package class08


/*
	int[] d, d[i]: i号怪兽的能力
	int[] p, p[i]: i号怪兽要求的钱

	开始时你的能力是0，你的目标是从0号怪兽开始，通过所有的怪兽。
	如果你当前的能力，小于i号怪兽的能力，你必须付出p[i]的钱，贿赂这个怪兽，
	然后怪兽就会加入你，它的能力直接累加到你的能力上；如果你当前的能力，大于
	等于第i号怪兽的能力，你可以选择直接通过，你的能力并不会下降，你也可以选择
	贿赂这个怪兽，然后怪兽就会加入你，它的能力直接累加到你的能力上。
	返回通过所有的怪搜，需要花的最小钱数。


	【解法一】
		使用递归，猜可能性的方式解。
		假设函数 f(d, p, start, ability) 的含义为：d,p为能力与钱的数组，
			start， ability 为开始位置，与当前能力的值
			函数的意思是，从start开始，且当前的能力为ability，到结束位置，
			最小花费的金钱的数量。

	【解法二】
		使用方法一，将start，和ability 转化为一个二维dp表，进行填值，该种
		方式的缺点是，ability很大的时候，dp表会非常大。

	【解法三】
		采用怪兽的数量与花费的金钱作为两个维度
		dp[i][j] 表示通关0-i个怪兽，严格花费j的情况下的最大能力值

		1. 算出花费的范围
		2. 第一列填值，
		3. 第二列填值
		4. dp[i][j] 可能来源于 dp[i-1][j] 或者 dp[i-1][j-当前花费]

	【错误解法：】
		使用动态规划，dp[i] 表示通关0-i需要花费的最小钱数，需要一个变量记录当前的
		能力值。
			1. [0 ... i-1] i
				1.a 到达i位置后，如果当前的能力值小于第i，则最小通过的i的钱为，dp[i-1]+d[i]
				1.b 到达i位置后，如果当前的能力值大于第i，则通过i的钱为，dp[i-1]

*/

//1. 【解法一】动态规划，递归尝试模型
// d[i]: i号怪兽的能力
// p[i]: i号怪兽要求的钱
func MinPassMoney(d, p []int) int {
	return MinPassMoneyProcess(d, p, 0, 0)
}

func MinPassMoneyProcess(d, p []int, start, ability int) int {
	if start == len(d) { // 最后的位置开始，已经没有怪兽了，返回花费0即可
		return 0
	}
	if ability < d[start] {
		return p[start] + MinPassMoneyProcess(d, p, start+1, ability+d[start])
	} else {
		return min(p[start] + MinPassMoneyProcess(d, p, start+1, ability+d[start]),
			MinPassMoneyProcess(d, p, start+1, ability))
	}
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

// 【解法三】采用怪兽的数量与钱的范围的维度，采用dp表解
// d[i]: i号怪兽的能力
// p[i]: i号怪兽要求的钱
func MinPassMoney3(d, p []int) int {
	maxMoney := 0
	for _, m := range p {
		maxMoney += m
	}
	N := len(d)
	dp := make([][]int, N)
	for i:=0; i<N; i++ {
		dp[i] = make([]int, maxMoney+1)
	}
	// 初始所有位置为 -1
	for i:=0; i<N; i++ {
		for j:=0; j<=maxMoney; j++ {
			dp[i][j] = -1
		}
	}
	// 填写第一列, 花费为0时，没有任何能力，所以不可能打过怪兽
	for i:=0; i<N; i++ {
		dp[i][0] = -1
	}
	// 填写第一行， 有且仅有攻克怪物0的花费时候刚好满足j位置
	for j:=0; j<=maxMoney; j++ {
		if j == p[0] {
			dp[0][j] = d[0]
		}
		dp[0][j] = -1
	}
	// d[i]: i号怪兽的能力
	// p[i]: i号怪兽要求的钱
	// 其他位置的依赖情况，x 位置
	//    		   j-p[i]	  j
	//    i-1		x	 	  x
	//    i		         	  c
	for i:=1; i<N; i++ {
		for j:=1; j<=maxMoney; j++ {
			// 可能性1
			if j-p[i] >= 0 && dp[i-1][j-p[i]] != -1 {
				dp[i][j] = dp[i-1][j-p[i]]+d[i]
			}
			// 可能性2
			if dp[i-1][j] >= d[i] {
				dp[i][j] = max(dp[i-1][j], dp[i][j])
			}
		}
	}
	ans := 0
	for j:=0; j<=maxMoney; j++ {
		if dp[N-1][j] != -1 {
			ans = j
			break
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}